package RealTim0;

// TODO 动态规划 | 贪心算法 [经典] 【-】 连续子数组的最大和
// TODO https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484

public class xqz0002 {

    public int FindGreatestSumOfSubArray (int[] array) {
        // dp[i] 表示 第i个位置所在 的 连续子数组的最大和
        int[] dp = new int[array.length];

        // 初始状态
        dp[0] = array[0];
        int res = dp[0];

        // 状态转移
        for(int i = 1; i < array.length; i++){
            dp[i] = Math.max(array[i],dp[i-1]+array[i]);
            res = Math.max(res,dp[i]);
        }
        return res;
    }

}
